1. Field of the Invention
This invention relates to overlapped multiple-bit scanning multiplication systems and, more particularly, to such systems having more than three scanning bits with a reduced partial product matrix which is banded.
2. Brief Description of the Prior Art
One of the most widely used techniques for binary multiplication has been the uniform overlapped shift method for 3-bit scanning proposed by MacSorley in "High-Speed Arithmetic in Binary Computers," Proceedings of the IRE, Vol. 99, January 1961, pp. 67-91, as a modification of the Booth algorithm disclosed in "A Signed Multiplication Technique," Quarterly Journal of Mechanical and Applied Math, Vol. 4, Part 2, 1951, pp. 236-240. Another 3-bit overlapped scanning scheme is shown in "Multiply-Addition--an Ultra High Performance Dataflow", IBM Technical Disclosure Bulletin, Vol. 30, No. 3, August 1987, pp. 982-987, the subject matter of which, at the time the present invention was made, was owned by the assignee of the present application. More than 3-bit overlapped scanning has seldom been used, primarily because it has required special hardware, possibly more chip area, and more difficult partial product selections. In view, however, of improvements in circuit densities over the past few years, and because more than 3-bit scanning may improve the overall speed of the multipliers, there have been several recent proposals for more than 3-bit overlapped scanning designs. See, for example, Waser et al., Introduction to Arithmetic for Digital System Designers, Chapter 4, CBS College Publishing, 1982, and Rodriguez, "Improved Approach to the Use of Booth's Multiplication Algorithm," IBM Technical Disclosure Bulletin, Vol. 27, No. 11, April 1985, pp. 6624-6632.
Multipliers of this type employ a matrix of the partial products selected in response to each scan. For summing the partial products in the matrix, carry save adder trees are typically used. Methods for reducing the trees have been suggested by Wallace in "A Suggestion for a Fast Multiplier," IEEE Trans. Electronic Computers, Vol. EC-13, Feb. 1964, pp. 14-17 and Dadda in "Some Schemes for Parallel Multipliers," Alta Frequenza, Vol. 34, March 1965, pp. 349-356. The method proposed by Dadda results in a hardware saving when compared to that of Wallace as is proven by Habibi et al. in "Fast Multipliers," IEEE Trans. On Computers, Feb. 1970, pp. 153-157. Mercy, U.S. Pat. No. 4,556,948, teaches a method to improve the speed of the carry save adder tree by skipping carry save adder stages. After the carry save adder tree reduces the number of term to two, the two terms are then added with a two-input 2-1 adder. Such 2-1 adders can be designed using conventional technology or some scheme for fast carry look ahead addition as proposed, for example, by Ling in "High-Speed Binary Adder", IBM J. Res. Develop., Vol. 25, No. 3, May 1981, pp. 156-166.